
%\subsection{Model}

\paragraph{Distributed Computing Model}
Consider an undirected, unweighted, connected $n$-node graph $G = (V, E)$.  Suppose that every node (vertex) hosts a processor with
unbounded computational power (though our algorithms only use time and space polynomial in $n$ at each vertex), but with only local knowledge initially.
%Specifically, assume that each node is associated with a distinct identity number from the set $\{1, 2, . . . , n\}$. At the beginning of the computation, each node $v$ accepts as input its own identity number and the identity numbers of its neighbors in $G$.
%\amitabh{recheck the anonymous assumption in the end, as Danupon mentioned}
%Specifically, assume that the network is \emph{anonymous}, i.e., the nodes do not have IDs but they do know their degrees, %i.e., number of neighbors.
We assume that nodes have unique identifiers.
The nodes may accept some additional inputs as specified by the problem at hand. The communication is synchronous, and occurs in discrete pulses, called {\em rounds}. Further, nodes can send messages to each of their neighbors in every round. \amitabh{Check the broadcast assumption too, in the end}
%allowed to communicate through the edges of the graph $G$.
 In our model, all the nodes wake up simultaneously at the beginning of round 1.
%, and from this point on the nodes always know the number of the current round \amitabh{Wonder if this assumption is needed. Leaving it in for now}.
 In each round
each node $v$ is allowed to send an arbitrary message subject to the bandwidth constraint of size
$O(\log n)$ bits through any edge $e = (v, u)$ that is adjacent to $v$,
and these messages will arrive at each corresponding neighbor at the end of the current round.
Our model is akin to the standard model of distributed computation known as the
{\em CONGEST model}~\cite{peleg}.
%Our model is weaker since the CONGEST model assumes unique IDs, point-to-point communication, and unlimited computation power at nodes (none of which we need).
 The message size constraint of CONGEST is very important for large-scale resource-constrained dynamic networks where running time is crucial.
% Now, we state our dynamicity conditions:
%This work addresses the
%problem of computing random walks in a time-efficient manner.

\paragraph{Edge-Dynamic Network Model}
We use the edge deletion/addition model; i.e., we consider a sequence of (undirected) graphs $G_0, G_1, \ldots$ on $n$ nodes, where, for any $t$, $G_t$ denotes the state of the dynamic network $G(V,E)$ at time $t$, where the adversary deletes and/or inserts upto $r$ edges at each step, i.e.,  $E(G_{t+1})= (E(G_{t})\setminus E_U) \cup E_V$, where $E_U \subseteq E(G_{t})$ and $E_V \subseteq E(\overline{G_{t}})$, $|E_U| + |E_V| \leq r$ (where $\overline{G_{t}}$ is the complement graph of $G_{t}$). The edge change rate is denoted by the parameter $r$.
% is assumed to be constant.

%either $E(G_t)=E(G_{t+1})\setminus e$ for some $e\in E(G_{t+1})$, or $E(G_{t+1})=E(G_{t})\setminus e$ for some $e\in E(G_{t})$.
Following the notion in \cite{KuhnOM11}, we define the {\em dynamic diameter} of the dynamic network $G(V,E)$, denoted by $D$, to be the maximum time a message needs to traverse the network at any time.
%Let $D_{\max}$ be the maximum diameter of the network at all time, i.e., $D_{\max}=\max_t D(G_t)$.
%We assume that the network is connected at all time.
More formally, dynamic diameter is defined as follows:
\begin{definition}[Dynamic Diameter (Adapted from \cite{KuhnOM11}, Definition 3)]
%{\bf Dynamic Diameter (~\cite{KuhnOM11}, Definition 3)}
We say that the dynamic network $G=(V,E)$ has a dynamic diameter of $D$ upto time $t$ if $D$ is the smallest positive integer such that, for all $t' \le t$ and $u,v \in V$, we have $(u,max\{0,t' - D\}) \leadsto (v,t')$, where, for each pair of vertices $x, y$ and times $t_1 \leq t_2$, $(x,t_1) \leadsto (y,t_2)$ means that at time $t_2$ node $y$ can receive direct information, through a chain of messages, originating from node $x$ at time $t_1$.
\end{definition}


Note that the nodes do not need to know the exact dynamic diameter $D$ but only a (loose) approximation to it. For simplicity, we assume henceforth that the nodes know the exact value of $D$.

% Note that this definition of dynamic diameter allows the graph to become disconnected, as long as messages never take more than $D$ rounds to get from one node to another. We assume that the dynamic diameter $D$ bounded and known to all the nodes in the network.

%\danupon{Need a more formal definition. See \cite{KuhnOM11}. We should also cite Gopal's SODA paper. They also talk about dynamic diameter.}
There are several measures of efficiency of distributed algorithms, but we will concentrate on one of them, specifically, {\em the running time}, that is, the number of rounds of distributed communication. (Note that the computation that is performed by the nodes locally is ``free'', i.e., it does not affect the number of rounds.)

%Note: Maybe, maintaining the network diameter at all time is also interesting (although it's quite easy).

%An alternative way to define the network and parameters: Let $T_c$ and $T_f$ to be a time to ``count'' and ``flood'' at any time in the course of the network change. We note that $T_c$ and $T_f$ could be bounded by $D_{max}$ which is the maximum diameter of the network at all time. (Should we define the model like this?)

%\amitabh{Adding a figure for the model. Modify as desired. We should probably combine the subsections. Also, sync the notations and exact model definition.}

%\newpage
\begin{figure*}[tb]
\caption{The  distributed Edge Insert and Delete Model.}
\label{algo: model-general}
\begin{boxedminipage}{\textwidth}
{\fontsize{10}{10}\selectfont
\begin{algorithmic}
\STATE Each node of $G_0$ is a processor.
\STATE Each processor starts with a list of its neighbors in $G_0$.
\STATE Pre-processing: Processors may exchange messages with their neighbors.
%send messages to and from their neighbors.
\FOR {$t := 1$ to $T$}
\STATE Adversary deletes and/or inserts upto $r$ edges at each step i.e.  $E(G_{t+1})=(E(G_{t})\setminus E_U) \cup E_V$, where $E_U \subseteq E(G_{t})$ and $E_V \subseteq{E(\overline{G_{t}})}$ (where $\overline{G_{t}}$ is the complement graph of $G_t$).
\IF{edge $(u,v)$ is inserted or edge $(u,v)$ is deleted}
\STATE Nodes $u$ and $v$ may update their information and exchange messages with their neighbors.
\STATE {\bf Computation phase:}
\STATE Nodes may communicate (synchronously, in parallel)
with their immediate neighbors. These messages are never lost or
corrupted, may contain the names of other vertices, and are received by the end of this phase.
\ENDIF
%\IF{edge $(u,v)$ is deleted}
%\STATE All neighbors of $v_t$ are informed of the deletion.
%\STATE During this phase, each node may add edges
%joining it to any other nodes as desired.
%Nodes may also drop edges from previous rounds if no longer required.
%\ENDIF
\STATE At the end of this phase, we call the graph $G_t$.
\ENDFOR
\vspace{5pt}
\hrule
\STATE {\bf Success metrics:}
%Minimize the following ``complexity'' measures: \COMMENT{Formally define here, and state as a minimization}
%Consider the graph  $G'$ which is the graph consisting solely of the original nodes and insertions without regard to
%deletions and healings. Graph $G'_{t}$ is $G'$ at timestep $t$ (i.e. after the $t^{\mathrm{th}}$ insertion or deletion).
%Graph $G'_{t}$ is $G'$ at timestep $t$ which is equivalent to $G'_{t'}$ where the $t' \le t$ is
%the timestep at which the latest insertion on or before $t$ occured.
%\begin{enumerate}
\begin{compactenum}
%\item{\bf Graph properties/invariants.}
\item{\bf Approximate Dense Subgraphs:} \emph{Graph $S'_T$:}
% {\bf FORMALLY DEFINE HERE}%\amitabh{Formally define here}
 The induced graph of a set $S'_T \subseteq V_T$, s.t., $\den(S'_T) \ge \frac{\den(S^{*}_T)}{\alpha}$, where  $S^{*}_T \subseteq V$, s.t., $\den(S^{*}_T) = \max \den(S_T)$ over all $S_T \subseteq V_T$.
\item{\bf Approximate at-least-k-Dense Subgraphs:} \emph{Graph $S^{k}_T$:} The induced graph of a set  $S^k \subseteq V, |S^k| \geq k$, s.t., $\den(S^k) \ge \frac{\den(S^{k*})}{\alpha}$, where   $S^{k*} \subseteq V, |S^{k*}| \geq k$, s.t., $\den(S^{k*}) = \max \den(S)$ over all $S \subseteq V, |S| \geq k$.

%{\bf FORMALLY DEFINE HERE}%\amitabh{Formally define here}
%\item{\bf k-core:}
  %$\max_{v \in G} degree(v,G_T) / degree(v,G'_T)$
%\item {\bf Network stretch.} $\max \left( (x,y) \in G_{t}, G_{t'}; t, t' <T, \distance_{t'}(x,y) / \distance_{t}(x,y)
%\right)$
%\item {\bf Network stretch.} $\max_{x, y \in G_{T}} \frac{dist(x,y,G_{T})}{dist(x,y,G'_{T})}$, where, for a graph $G$ and nodes $x$ and $y$ in $G$, $dist(x,y,G)$ is the
%length of the shortest path between $x$ and $y$ in $G$.
%For any pair of nodes $x$ and $y$, $ \distance(x,y,G_{T}) / \distance(x,y,G'_t)$
\item{\bf Communication per edge.} The maximum number of bits sent across a single edge in a single recovery round. $O(\log n)$ in CONGEST model.
% \tom{Want to modify this or omit?}
\item{\bf Computation time.} The maximum total time (rounds) for all nodes to compute their density estimations starting from scratch assuming it takes a message no more than $1$ time unit to traverse any edge and we have unlimited local computational power at each node. %{\bf CAN WE SEPERATE INTO WORST CASE AND AMORTIZED HERE} %\amitabh{Can we seperate into worst case and amortized here}
%\end{enumerate}
\end{compactenum}
\end{algorithmic}
} %end of setspace
\end{boxedminipage}
\end{figure*}

%\afterpage{\clearpage}
